package com.xhj.joffer.linkedList;
import org.junit.Test;

import java.util.HashMap;
/**
 * @author haijianxia pure_xhj@163.com
 * @Date 2021-09-22
 * @Time 11:40
 */
public class FindLinkedCircularListGate {
  public static void main(String[] args) {
	  LinkedListNodeOne root=new LinkedListNodeOne("root");
	  LinkedListNodeOne gate9=new LinkedListNodeOne("gate9");
	  root
//		  .next(new LinkedListNodeOne("r2"))
//		  .next(new LinkedListNodeOne("r3"))
//		  .next(new LinkedListNodeOne("r4"))
//		  .next(new LinkedListNodeOne("r5"))
//		  .next(new LinkedListNodeOne("r6"))
//		  .next(new LinkedListNodeOne("r7"))
//		  .next(new LinkedListNodeOne("r8"))
		  .next(gate9)
//		  .next(new LinkedListNodeOne("r10"))
//		  .next(new LinkedListNodeOne("r11"))
//		  .next(new LinkedListNodeOne("r12"))
		  .next(new LinkedListNodeOne("r13"))
		  .next(gate9);
    System.out.println(root.toStringTail());
    System.out.println("test01(root).toString() = " + test01(root).toString());

    System.out.println("====================================================");
    System.out.println("test02(root).toString() = " + test02(root).toString());

  }
	/** 思路二: 记录地址值, 是否相同 */
	@Test
	public static LinkedListNodeOne test01(LinkedListNodeOne head) {
		System.out.println("\n=============test01==============");
		System.out.println("思路二: 记录地址值, 是否相同");
		long time01 = System.currentTimeMillis();
		
		LinkedListNodeOne result = null;
    if (head != null){
    	// 判断是否有next==null;
	    LinkedListNodeOne nodeNow=head;
	    HashMap<LinkedListNodeOne,Integer> hashMap=new HashMap<>();
	    while(nodeNow!=null){
		    if(hashMap.containsKey(nodeNow)){
		      result=nodeNow;
		      break;
		    }
		    hashMap.put(nodeNow,1);
		    nodeNow=nodeNow.next;
	    }
    }

		long time0101  = System.currentTimeMillis() - time01;
		System.out.println("test01 耗时 =  " + time0101  + "ms");
		System.out.println("=================================");
	
		return result;
	}

	/** 思路一: 双指针 */
	@Test
	public static LinkedListNodeOne test02(LinkedListNodeOne head) {
		System.out.println("\n=============test02==============");
		System.out.println("思路一: 双指针");
		long time02 = System.currentTimeMillis();

		LinkedListNodeOne result =null;
		LinkedListNodeOne fast=head, slow=head;
		int times=0, time1=0;
		// a+n*b+c=times n可以为0, b>=1
 		while (fast!=null && slow!=null){
			times++;
			fast=fast.next.next;
			slow=slow.next;
			if (fast == null) {
				break;
			}else{
				if (fast == slow) {
					if(time1!=0){
					  break;
					}
					time1=times;
				}
			}
		}
		LinkedListNodeOne nodeNow=null;
		int time2=0, timeResult=(times-time1);
		while(time2<timeResult){
			result=nodeNow;
		}

		long time0202  = System.currentTimeMillis() - time02;
		System.out.println("test02 耗时 =  " + time0202  + "ms");
		System.out.println("=================================");

		return result;
	}
}
